package com.chongzi.cloud;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class code912 {//快速排序

    public static void main(String[] args) {
        int[] data = {9, -16, 40, 23, -30, -49, 25, 21, 30};
        sortArray(data);
        System.out.println(Arrays.toString(data));
    }


    public static int[] sortArray(int[] nums) {
        qSort(nums, 0, nums.length - 1);
        return nums;

    }

    private static void qSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivotIndex = partition(nums, left, right);
        qSort(nums, left, pivotIndex - 1);
        qSort(nums, pivotIndex + 1, right);

    }

    private static int partition(int[] nums, int left, int right) {
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        swap(nums, left, idx);
        int pv = nums[left];
        int i = left + 1;
        int j = right;
        while (i <= j) {
            while (i <= j && nums[i] < pv) {
                i++;

            }
            while (i <= j && nums[j] > pv) {
                j--;

            }
            if (i <= j) {
                swap(nums, i, j);
                i++;
                j--;

            }
        }
        swap(nums,  left, j);
        return j;

    }

    static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }


}
